package problem.year2021.march;

import java.util.Arrays;

/**
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * 示例 1:
 * 输入: 2
 * 输出: [0,1,1]
 * 示例 2:
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 * 进阶:
 * 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
 * 要求算法的空间复杂度为O(n)。
 * 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
 */
public class March3 {

    /**
     * 方法一需要对每个数遍历其二进制表示的每一位。可以换一个思路，当计算 iii 的「一比特数」时，如果存在 0≤j<i0 \le j<i0≤j<i，jjj 的
     * 「一比特数」已知，且 iii 和 jjj 相比，iii 的二进制表示只多了一个 111，则可以快速得到 iii 的「一比特数」。
     * <p>
     * 令 bits[i]\textit{bits}[i]bits[i] 表示 iii 的「一比特数」，则上述关系可以表示成：bits[i]=bits[j]+1\textit{bits}[i]=
     * \textit{bits}[j]+1bits[i]=bits[j]+1。
     * <p>
     * 对于正整数 xxx，如果可以知道最大的正整数 yyy，使得 y≤xy \le xy≤x 且 yyy 是 222 的整数次幂，则 yyy 的二进制表示中只有最高位是 111，
     * 其余都是 000，此时称 yyy 为 xxx 的「最高有效位」。令 z=x−yz=x-yz=x−y，显然 0≤z<x0 \le z<x0≤z<x，则 bits[x]=bits[z]+1\textit{bits}[x]=\textit{bits}[z]+1bits[x]=bits[z]+1。
     * <p>
     * 为了判断一个正整数是不是 222 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 yyy 是 222 的整数次幂，则 yyy 的二进制表示中
     * 只有最高位是 111，其余都是 000，因此 y&(y−1)=0y \&(y-1)=0y&(y−1)=0。由此可见，正整数 yyy 是 222 的整数次幂，当且仅当 y&(y−1)=0y \&(y-1)=0y&(y−1)=0。
     * <p>
     * 显然，000 的「一比特数」为 000。使用 highBit\textit{highBit}highBit 表示当前的最高有效位，遍历从 111 到 num\textit{num}num
     * 的每个正整数 iii，进行如下操作。
     * <p>
     * 如果 i&(i−1)=0i \&(i-1)=0i&(i−1)=0，则令 highBit=i\textit{highBit}=ihighBit=i，更新当前的最高有效位。
     * <p>
     * iii 比 i−highBiti-\textit{highBit}i−highBit 的「一比特数」多 111，由于是从小到大遍历每个数，因此遍历到 iii 时，
     * i−highBiti-\textit{highBit}i−highBit 的「一比特数」已知，令 bits[i]=bits[i−highBit]+1\textit{bits}[i]=\textit{bits}
     * [i-\textit{highBit}]+1bits[i]=bits[i−highBit]+1。
     * 最终得到的数组 bits\textit{bits}bits 即为答案。
     *
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        // num 有num+1个结果集
        int len = num + 1;
        int[] answer = new int[len];
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            answer[i] = answer[i - highBit] + 1;
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new March3().countBits(7)));
    }
}
